package a07_二叉树;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

/**
 * <p>
 * a10_二叉树的所有路径
 * </p>
 *      1
 *   2     3
 *     5
 * 1,2,5    1,3
 * 1、选择遍历顺序
 *    选择前序遍历的原因：只有前序遍历才能输出125和13
 * 2、本题的递归为啥有回溯的过程
 *    当收集到1,2,5以后，将2,5弹出去，回归到1，然后再去收集3的过程就叫做回溯
 *
 * @author flyduck
 * @since 2024-08-30
 */
public class a13_二叉树的所有路径复习1 {


    public static void main(String[] args) {
//        Deque<Integer> path = new LinkedList<>();
//        path.addFirst(1);
//        path.addFirst(2);
//        System.out.println(path.pollLast());

        TreeNode treeNode = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(4),
                        new TreeNode(5)
                ),
                new TreeNode(3,
                        new TreeNode(6),
                        new TreeNode(7)
                )
        );
        List<String> list = binaryTreePaths(treeNode);
        System.out.println();
    }

    public static List<String> binaryTreePaths(TreeNode root) {
        Stack<Integer> path = new Stack<>();
        List<String> resultList = new ArrayList<>();
        traversal(root, path,resultList);
        return resultList;
    }

    public static void traversal(TreeNode node,Stack<Integer> path,List<String> resultList){
        if(node != null){
            path.add(node.val);
        }
        if(node != null && node.left == null && node.right == null){
            //到了跟节点了：但是跟节点还没到path里面，所以中放在最前面
            String result = path.stream()
                    .map(i -> i.toString())
                    .collect(Collectors.joining("->"));
            resultList.add(result);
        }

        if(node.left != null){
            traversal(node.left, path, resultList);
            path.pop();
        }

        if(node.right != null){
            traversal(node.right, path, resultList);
            path.pop();
        }
    }



    /**
     *     1
     *    2 3
     * 以1->2这个路径为例子
     * 如果最后一次迭代node为null，那么2的left和right都会进来将1->2都统计一次
     * @param node
     * @param path 单条路径
     * @param resultList 多个路径的结果
     */
//    public static void traversal(TreeNode node, Stack<Integer> path, List<String> resultList){
//        if(node == null){//终止条件：如果到了叶子节点，收集元素
//            String result = path.stream()
//                    .map(i -> i.toString())
//                    .collect(Collectors.joining("->"));
//            resultList.add(result);
//            return;
//        }
//        path.add(node.val);//中进来
//        traversal(node.left,path,resultList);//统计左的路径，并且
//        if (node.left != null) {
//            path.pop();
//        }
//        traversal(node.right,path,resultList);
//        if (node.right != null) {
//            path.pop();
//        }
//    }

}
